package com.sicheng.lc.lc笔试.神策篇;

import java.util.*;

public class 罗马 {

    static int N = (int) 1e6 * 3;

    /**
     * 罗马编号为始终是1，其他城市编号都大于1
     * 各城市有道路相连 组成一颗树形结构 a,b从出发点只朝着罗马前进问最早相遇在那座城市
     * a，b可以停下等对方，也可以走
     * 输入描述：
     * 第一行 n 表示n条道路两
     * 接下来n行 每行2个数 道路2端的城市编号
     * 最后一行是2座出发城市
     *
     * 输出描述：
     * 输出一行 ： 相遇最早的城市
     */
    public static void main(String[] args) {
        // write your code here

        // 题目很类似最近公共祖先
        // 使用标记法lca 只跑80%
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Integer>[] g = new List[N + 1];
        Arrays.setAll(g, k -> new ArrayList<Integer>(10));
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            g[a].add(b);
            g[b].add(a);
        }
        int a = sc.nextInt(), b = sc.nextInt();

        ArrayDeque<Integer> q = new ArrayDeque<>();

        int[] p = new int[N + 1];
        boolean[] st = new boolean[N + 1];
        st[1] = true;
        q.add(1);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int x = q.poll();
                for (int y : g[x]) {
                    if (!st[y]) {
                        p[y] = x;
                        st[y] = true;
                        q.offer(y);
                    }
                }
            }
        }

        boolean[] v = new boolean[N + 1];
        mark(v, p, a);
        int j = mark(v, p, b);
        System.out.println(j);
    }

    static int mark(boolean[] v, int[] p, int x) {
        for (int i = x; i >= 1; i = p[i]) {
            if (v[i])
                return i;
            v[i] = true;
        }
        return -1;
    }
}
